All Questions
15 questions
0votes
0answers
49views
Min cost perfect matching, but with conflicting edge pairs
Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \...
- 649
4votes
1answer
157views
Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?
I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
- 649
2votes
1answer
131views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 948
0votes
0answers
161views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there. I am ...
5votes
0answers
188views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem. If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
- 649
1vote
0answers
101views
Are the intermediary sets in maximum cardinality search optimal in some way?
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
- 2,292
0votes
1answer
256views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
- 11
4votes
0answers
2kviews
Optimizing Maximum Weighted Matching (Edmonds Blossom)
Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation was ...
- 241
4votes
1answer
4kviews
Minimal Cost of Eulerian Path
Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
- 241
5votes
1answer
510views
Modifying Edmonds' Blossom Algorithm
Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...
- 241
4votes
2answers
771views
Optimization Problem on a Directed Graph
I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
- 45
3votes
1answer
981views
Subset of a bipartite graph with maximal number of minimal unmatched vertices
Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all $(...
3votes
1answer
275views
Minimum length walk from s to t covering a subset of vertices
I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), $...
- 263
0votes
1answer
3kviews
Linear Programming with Modulo Linear Constraints
Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as: find feasible point s.t. $\min \sum_{ij}v_{ij}$ for all $(i,j)$ in $E$ $z_{ij} \le (c_i - c_j) \bmod k$ (i) $z_{ij} \le (...
- 745
7votes
2answers
594views
Capacitated multiple vehicle routing problem with handovers
I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
- 121
